package com.hyb.algorithm.data.struct.dp;

/**
 * @author: ybhu
 * @create: 2021/08/31 08:38
 *
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
 * https://labuladong.gitbook.io/algo/mu-lu-ye-2/mu-lu-ye-4/tuan-mie-gu-piao-wen-ti
 * 122. 买卖股票的最佳时机 II
 */
public class MaxProfit2 {

    /**
     * 竖的坐标是 0,1 代表
     * 0代表 手里没有股票的最大利润
     * 1代表  手里有1只股票的最大利润
     * 状态转移方程  dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i])
     * dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {

        if(prices.length<=0){
            return 0;
        }
        int n=prices.length;
        int[][] dp=new int[n][2];



        for(int i=0;i<n;i++){

            if(i==0){
                //  dp[i][0]= Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
                dp[i][0]=0;
                dp[i][1]=-prices[i];
                continue;
            }

            dp[i][0]= Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]= Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }

        return dp[n-1][0];
    }
}
